//===- SuperwordLevelParallelism.cpp - Superword Level Parallelism --------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This transformation implements the Superword Level Parallelism algorithm
// described in Samuel Larsen , Saman Amarasinghe, Exploiting superword level
// parallelism with multimedia instruction sets, Proceedings of the ACM SIGPLAN
// 2000 conference on Programming language design and implementation, p.145-156,
// June 18-21, 2000, Vancouver, British Columbia, Canada..
//

//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "slp"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/Module.h"
#include "llvm/Instructions.h"
#include "llvm/Constants.h"
#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "list"
using namespace llvm;
using namespace std;

STATISTIC(NumStmtsPacked,  "Number of total statements packed");
STATISTIC(NumPacks,  "Number of total packs scheduled");
STATISTIC(NumPacksBroken,  "Number of packs broken because of dependence");

namespace {
  //--------------------------------------------------------------------------//
  // class SLP: Superword Level Parallelism function pass.
  // 
  // The main entry point is runOnBasicBlock.
  // The pass is registered using the declaration of a static global
  // variable (X) below.
  //--------------------------------------------------------------------------//
  
  struct SLP : public BasicBlockPass {
    static char ID;             // Pass identification
    
    SLP() : BasicBlockPass(ID) { }

    // Entry point for the overall scalar-replacement pass
    bool runOnBasicBlock(BasicBlock &BB);

    // getAnalysisUsage - This pass does not require any passes, but we know it
    // will not alter the CFG, so say so.
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<AliasAnalysis>();
      AU.addRequired<MemoryDependenceAnalysis>();
      
      AU.addRequiredTransitive<AliasAnalysis>();
      AU.addPreserved<MemoryDependenceAnalysis>();
      AU.addRequiredTransitive<ScalarEvolution>();
    }


  private:
    //std::vector<Instruction*> Pack;  //The structure we use to express instruction pack
    set< vector<Instruction*> > PackSet; //Used to contain all the candidate instruction pack
    MemoryDependenceAnalysis *MD;
    AliasAnalysis *AA;
    ScalarEvolution *SE; //used to evaluate two pointers are ajacent
    enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 };
    
    const TargetData *TD;

    void printPack(vector<Instruction*>& Pack);//Utility function to dump current Packset
    void printPackSet(set< vector<Instruction*> >& PackSet);//Utility function to dump current Packset

    bool isomorphic(Instruction* s1, Instruction* s2) {
      //If two instructions have the same ID, same type and same number of operands, they are isomorphic
      if(s1->getValueID() != s2->getValueID()) { return false; }
      if(s1->getType() != s2->getType()) { return false; }
      if(s1->getNumOperands() != s2->getNumOperands()) { return false; }
      unsigned numOperands = s1->getNumOperands();
      for(unsigned i = 0; i< numOperands; i++) {
          if(s1->getOperand(i)->getType() != s2->getOperand(i)->getType()) { return false; }
      }
      return true;
    };
    bool hasMemRef(Instruction* I); //if a statement accesses memory (Load/Store)
    bool adjacent(Instruction* s1, Instruction* s2); //checks adjacency between two memory references

    bool hasMemoryWrite(Instruction* I); //checks if the statement modifies memory
    bool haveDataDependence (Instruction* I, Instruction* J); //Check I and J has def-use relationship
    bool indepedent(Instruction* s1, Instruction* s2); //checks the stmts have no dependence
    
    
    static bool IsMemRefInstr(const Instruction *I) {
      return (I->mayReadFromMemory() || I->mayWriteToMemory());
    }
    static Value* GetPointerOperand(Instruction *I);
    static bool IsLoadOrStoreInst(const Instruction *I);
    bool isDependencePair(const Instruction *I, const Instruction *J);
    AliasAnalysis::AliasResult UnderlyingObjectsAlias(AliasAnalysis *AA,
                                                         const Value *A,
                                                         const Value *B);
    DependenceResult analysePair(Instruction* I, Instruction* J);

    bool followUseDefs(BasicBlock &BB, vector<Instruction*>& Pack, vector<vector<Instruction*> >& workPackList);
    bool followDefUses(BasicBlock &BB, vector<Instruction*>& Pack, vector<vector<Instruction*> >& workPackList);
    int  estSavings(vector<Instruction*>& Pack);
    
    vector<Instruction*> joinPacks(vector<Instruction*>& Pack1, vector<Instruction*>& Pack2);

    bool stmtsCanPack(Instruction* s1, Instruction* s2, unsigned align);
    bool findAdjRefs(BasicBlock &BB);
    void extendPacklist(BasicBlock &BB);
    void combinePacks();

    vector<Instruction*> containingPackSet(Instruction* s);
    void splitFirstUnscheduledPack(BasicBlock &BB, set<Instruction*> &ScheduledISet);
    bool depsScheduled(set<Instruction*> &UnScheduledISet, Instruction* inst);
    bool schedule(BasicBlock &BB); //do code schedule

    void emitCode(BasicBlock &BB); //transform PackSet into vector instructions
    Constant* genInsertelementConsts(vector<Constant*> &consts);
    Instruction* genInsertelementInsts(vector<Value*> &insts, vector<Instruction*> &outInsts); //used for vector inst's operand
    void genExtractelementInsts(Instruction* inst, vector<Instruction*> &outInsts); //used for vector inst's result
    // Add fields and helper functions for this pass here.
  };
}

//--------------------------------------------------------------------------//
// Register the pass so it is accessible from the command line,
// via the pass manager.
//--------------------------------------------------------------------------//
char SLP::ID = 0;
static RegisterPass<SLP> X("slp", "Superword Level Parallelism transformation");

void SLP::printPack(vector<Instruction*>& Pack) {
  for(unsigned i=0; i<Pack.size(); i++) {
    errs() << * Pack[i] << "\n";
  }
}

void SLP::printPackSet(set< vector<Instruction*> >& PackSet) {
  unsigned i = 0;
  errs() << "[PackSet Size:"<< PackSet.size() << "]\n{\n";
  for(set< vector<Instruction*> >::iterator it=PackSet.begin(); it!=PackSet.end(); it++) {
    vector<Instruction*> Pack = *it;
    //Iterate each Pack
    errs() << "[Set]" << i++ <<"\n";
    printPack(Pack);
  }
  errs() << "}\n";
}

/*
 * Only two cases identified right now: LoadInst/StoreInst
 */
bool SLP::hasMemRef(Instruction* I) {
  if(StoreInst::classof(I) || LoadInst::classof(I)) {
      return true;
  }
  return false;
}

/*
 * Check the two input instrs (Both Load or Store)'s ptr are ajacent
 * How to define adjacent:  (ptr2 - ptr1) == Load/Store's type's width
 * e.g. int load/store, type width is 4 byte. ptr2-ptr1 should be 4.
 */
bool SLP::adjacent(Instruction* s1, Instruction* s2) {
  //Quick check the isomorphic
  if(!isomorphic(s1,s2)) {
    return false;
  }

  Value *V1, *V2; //store the two pointers
  Type* instType;
  if(LoadInst::classof(s1)) {
    LoadInst* LI1 = cast<LoadInst>(s1);
    LoadInst* LI2 = cast<LoadInst>(s2);
    instType = LI1->getType();
    V1 = LI1->getPointerOperand();
    V2 = LI2->getPointerOperand();
  }

  if(StoreInst::classof(s1)) {
    StoreInst* ST1 = cast<StoreInst>(s1);
    StoreInst* ST2 = cast<StoreInst>(s2);
    instType = ST1->getOperand(0)->getType();
    V1 = ST1->getPointerOperand();
    V2 = ST2->getPointerOperand();
  }
  uint64_t ajacentSize;
  uint64_t UnknownSize = ~UINT64_C(0);
  ajacentSize = TD && instType->isSized() ? (TD->getTypeSizeInBits(instType) +7) / 8 : UnknownSize;

  errs() << "[adjacent]evaluation two ptrs:" << *V1 << ";" <<*V2 <<"\n";
  //Use SCEV to do computation
  const SCEV *AS = SE->getSCEV(V1);
  const SCEV *BS = SE->getSCEV(V2);
  const SCEV *BA = SE->getMinusSCEV(BS, AS); //pointer difference

  const SCEV *BW = SE->getConstant(AS->getType(), ajacentSize, true); //type width
  const SCEV *BABW = SE->getMinusSCEV(BW, BA); // pointer difference - type width
  
  
  if(BABW->isZero()) {
      errs() << "   Adjacent\n";
      return true;
  }
  else {
      errs() << "   Not ajacent. Diff: " << *BA << " ; Should be: " <<  *BW  << "\n";
      return false;
  }
  return false;
}

bool SLP::hasMemoryWrite(Instruction* I) {
  if (isa<StoreInst>(I))
    return true;
  return false;
}

bool SLP::IsLoadOrStoreInst(const Instruction *I) {
  // Returns true if the load or store can be analyzed. Atomic and volatile
  // operations have properties which this analysis does not understand.
  if (const LoadInst *LI = dyn_cast<const LoadInst>(I))
    return LI->isUnordered();
  else if (const StoreInst *SI = dyn_cast<const StoreInst>(I))
    return SI->isUnordered();
  return false;
}



bool SLP::isDependencePair(const Instruction *I, const Instruction *J) {
  return IsMemRefInstr(I) && IsMemRefInstr(J) && 
	 (I->mayWriteToMemory() || J->mayWriteToMemory());
}

Value* SLP::GetPointerOperand(Instruction* I) {
  if (LoadInst *LI = dyn_cast<LoadInst>(I))
  return LI->getPointerOperand();
  if (StoreInst *SI = dyn_cast<StoreInst>(I))
  return SI->getPointerOperand();
  return NULL; // unreachable
}

AliasAnalysis::AliasResult SLP::UnderlyingObjectsAlias(AliasAnalysis *AA,
                                                         const Value *A,
                                                         const Value *B) {
  const Value *aObj = GetUnderlyingObject(A);
  const Value *bObj = GetUnderlyingObject(B);
  return AA->alias(aObj, AA->getTypeStoreSize(aObj->getType()),
                   bObj, AA->getTypeStoreSize(bObj->getType()));
}


SLP::DependenceResult SLP::analysePair(Instruction* I, Instruction* J) {
  errs() << "[Dependence Analysis]" << "Analysing\n"<< *I << "\n" << *J << "\n";
  // We only analyse loads and stores but no possible memory accesses by e.g.
  // free, call, or invoke instructions.
  if (!IsLoadOrStoreInst(I) || !IsLoadOrStoreInst(J)) {
    errs() << "--> [?] no load/store\n";
    return Unknown;
  }

  Value *IPtr = GetPointerOperand(I);
  Value *JPtr = GetPointerOperand(J);
  //errs() << "---> " << *IPtr << " and " << *JPtr << "\n";
  switch (UnderlyingObjectsAlias(AA, IPtr, JPtr)) {
    case AliasAnalysis::MayAlias:
    case AliasAnalysis::PartialAlias:
      // We can not analyse objects if we do not know about their aliasing.
      errs() << "---> [?] may alias\n";
      return Unknown;

    case AliasAnalysis::NoAlias:
      // If the objects noalias, they are distinct, accesses are independent.
      errs() << "---> [I] no alias\n";
      return Independent;

    case AliasAnalysis::MustAlias:
      errs() << "---> [D] must alias\n";
      break; // The underlying objects alias, test accesses for dependence.
  }

//   const GEPOperator *IGEP = dyn_cast<GEPOperator>(IPtr);
//   const GEPOperator *JGEP = dyn_cast<GEPOperator>(JPtr);
// 
//   if (!IGEP || !JGEP)
//     return Unknown;
// 
//   // FIXME: Is filtering coupled subscripts necessary?
// 
//   // Collect GEP operand pairs (FIXME: use GetGEPOperands from BasicAA), adding
//   // trailing zeroes to the smaller GEP, if needed.
//   typedef SmallVector<std::pair<const SCEV*, const SCEV*>, 4> GEPOpdPairsTy;
//   GEPOpdPairsTy opds;
//   for(GEPOperator::const_op_iterator IIdx = IGEP->idx_begin(),
//                                      IEnd = IGEP->idx_end(),
//                                      JIdx = JGEP->idx_begin(),
//                                      JEnd = JGEP->idx_end();
//       IIdx != IEnd && JIdx != JEnd;
//       IIdx += (IIdx != IEnd), JIdx += (JIdx != JEnd)) {
//     const SCEV* ISCEV = (IIdx != IEnd) ? SE->getSCEV(*IIdx) : GetZeroSCEV(SE);
//     const SCEV* JSCEV = (JIdx != JEnd) ? SE->getSCEV(*JIdx) : GetZeroSCEV(SE);
//     opds.push_back(std::make_pair(ISCEV, JSCEV));
//   }
// 
//   if (!opds.empty() && opds[0].first != opds[0].second) {
//     // We cannot (yet) handle arbitrary GEP pointer offsets. By limiting
//     //
//     // TODO: this could be relaxed by adding the size of the underlying object
//     // to the first subscript. If we have e.g. (GEP x,0,i; GEP x,2,-i) and we
//     // know that x is a [100 x i8]*, we could modify the first subscript to be
//     // (i, 200-i) instead of (i, -i).
//     return Unknown;
//   }
// 
//   // Now analyse the collected operand pairs (skipping the GEP ptr offsets).
//   for (GEPOpdPairsTy::const_iterator i = opds.begin() + 1, end = opds.end();
//        i != end; ++i) {
//     Subscript subscript;
//     DependenceResult result = analyseSubscript(i->first, i->second, &subscript);
//     if (result != Dependent) {
//       // We either proved independence or failed to analyse this subscript.
//       // Further subscripts will not improve the situation, so abort early.
//       return result;
//     }
//     P->Subscripts.push_back(subscript);
//   }
//   // We successfully analysed all subscripts but failed to prove independence.   
  return Dependent;
}
/*
 * Check I and J has def-use relationship
 * Only check one step.
 */
bool SLP::haveDataDependence (Instruction* I, Instruction* J) {
  for (User::op_iterator it = J->op_begin(), e = J->op_end(); it != e; ++it) {
    Value *V = *it;
    if(I == V)
      return true;
  }
  for (User::op_iterator it = I->op_begin(), e = I->op_end(); it != e; ++it) {
    Value *V = *it;
    if(J == V)
      return true;
  }
  return false;
}

bool SLP::indepedent(Instruction* s1, Instruction* s2) {
  
  // First check whether there is any direct data dependence between the two statements. 
  // If an indirect dependency exists, it would be caught while scheduling
  
  if(haveDataDependence(s1, s2)) {
    errs() << "[DataDependence]Not independent:\n"<< *s1 <<"\n"<< *s2 <<"\n";  
    return false;
  }
  //TODO: Not sure if we really require memory dependence analysis here. 
  // two isomorphic loads can never have memory dependency.
  // two stores can have WAW dependency in memory but in that case they 
  // are not adjacent in memory and hence would never qualify as a pack pair.
  
  if (!isDependencePair(s1, s2))       
    return true;
  
  MemDepResult mdr1 = MD->getDependency(s1);
  MemDepResult mdr2 = MD->getDependency(s2);
  errs() << "[Independent-Memdep]\n"<< *s1 <<"\n"<< *(mdr1.getInst()) << "\n" << *s2 << "\n" << *(mdr2.getInst())<<"\n";
  
  if(s2 == mdr1.getInst() || s1 == mdr2.getInst()) {
      errs() << "[Independent-MemDep]\n" << *s1 << "\n" << *s2 << "\n";
      return false;
  }
  return true;
}

bool SLP::stmtsCanPack(Instruction* s1, Instruction* s2, unsigned align) {
  //TODO: We don't know align yet. The problem here is align is not known for getelementptr
  if(!isomorphic(s1,s2)) { //Check isomorphic
    return false;
  }

  if(!indepedent(s1,s2)) {
    return false;
  }
  //now we may create one pair. However, we must make sure s1 was not used in left, and s2 was not used in right

  for(set< vector<Instruction*> >::iterator it=PackSet.begin(); it!=PackSet.end(); it++) {
    vector<Instruction*> Pack = *it;
    if(Pack[0] == s1 || Pack[1] == s2) {
      return false; //used before
    }
  }
  //new pair
  return true;
}

bool SLP::findAdjRefs(BasicBlock &BB) {
  bool changed = false;
  //Wrong code to test the PrintPackSet
  Instruction* s1 = NULL;
  Instruction* s2 = NULL;
  for (BasicBlock::iterator IR1 = BB.getInstList().begin(); IR1 != BB.getInstList().end(); ++IR1){
    s1 = &(*IR1);
    for (BasicBlock::iterator IR2 = BB.getInstList().begin(); IR2 != BB.getInstList().end(); ++IR2){
      s2 = &(*IR2);
      //Main Part of the detection
      if(s1 == s2 ) { continue; }
      //analysePair(s1,s2);
      if(!hasMemRef(s1) || !hasMemRef(s2)) { continue; }
      if(adjacent(s1,s2)) {
        if(stmtsCanPack(s1,s2,0)) {
          errs() << "[findAdjRefs]found ADJRef:" << *s1 << "; "<< *s2 <<"\n";
          vector<Instruction*> Pack;
          Pack.push_back(s1);
          Pack.push_back(s2);
          PackSet.insert(Pack);
          changed = true;
        }
      }

    }
  }
  return changed;
}

int SLP::estSavings(vector<Instruction*>& Pack) {
  // TODO: estimate the gain if this pack is added to the PackSet
  return 1;
}

bool SLP::followUseDefs(BasicBlock &BB, vector<Instruction*>& Pack, vector<vector<Instruction*> >& workPackList) {
  bool changed = false;
  //ASSERT: pack consists of just 2 instructions
  if(Pack.size() != 2) {
    errs() << "Error: Found pack of size " << Pack.size();
    return false;
  }
  Instruction *s1, *s2;
  if((s1 = dyn_cast<Instruction> (Pack[0])) && (s2 = dyn_cast<Instruction> (Pack[1]))) {
    // TODO: unsigned align = getAlignment(s1);
    unsigned align = 0;
    // s1 and s2 are isomorphic statements and hence have same number of operands
    for (User::op_iterator i1 = s1->op_begin(), e1 = s1->op_end(), i2 = s2->op_begin(), e2 = s2->op_end(); i1 != e1 || i2 != e2; ++i1, ++i2) {
      Value *v1 = *i1;
      Value *v2 = *i2;
      Instruction *t1, *t2;
      if((t1 = dyn_cast<Instruction> (v1)) && (t2 = dyn_cast<Instruction> (v2))) {
	if ((t1 != t2) && (t1->getParent() == &BB) && (t2->getParent() == &BB) && stmtsCanPack(t1, t2, align)) { 
	  // Create a new pack with instructions t1 and t2
	  //we must create a packset in heap. Move
	  vector<Instruction*> newPack;
	  newPack.push_back(t1);
	  newPack.push_back(t2);
	  
 	  errs() <<"UD 1." << *t1 << "\n";
 	  errs() <<"UD 2." << *t2 << "\n";
	  
	  if(estSavings(newPack) >= 0) {
	    workPackList.push_back(newPack);
	    //TODO: setAlignment(s1, s2, align);
	    changed = true;
	  }
	}
      }
    }
  }  
  return changed;
}

bool SLP::followDefUses(BasicBlock &BB, vector<Instruction*>& Pack, vector<vector<Instruction*> >& workPackList) {
  bool changed = false;
  //ASSERT: Pack consists of just 2 instructions
  if(Pack.size() != 2) {
    errs() << "Error: Found pack of size " << Pack.size();
    return false;
  }
  Instruction *s1, *s2;
  if((s1 = dyn_cast<Instruction> (Pack[0])) && (s2 = dyn_cast<Instruction> (Pack[1]))) {
    // s1 and s2 are isomorphic statements and hence have same number of operands
    // TODO: unsigned align = getAlignment(s1);
    unsigned align = 0;
    int savings = -1;
    Instruction *u1, *u2;
    for (Value::use_iterator i1 = s1->use_begin(), e1 = s1->use_end(); i1 != e1; ++i1) {
      if (Instruction *t1 = dyn_cast<Instruction>(*i1)) {
	for (Value::use_iterator i2 = s2->use_begin(), e2 = s2->use_end(); i2 != e2; ++i2) {
	  if (Instruction *t2 = dyn_cast<Instruction>(*i2)) {
	    if ((t1 != t2) && (t1->getParent() == &BB) && (t2->getParent() == &BB) && stmtsCanPack(t1, t2, align)) { 
	      // Create a new pack with instructions t1 and t2
	      vector<Instruction*> newPack;
	      newPack.push_back(t1);
	      newPack.push_back(t2);
	      
	      if(estSavings(newPack) > savings) {
		savings = estSavings(newPack);
		u1 = t1;
		u2 = t2;
	      }
	    }
	  }
	}
      }
    }
    if (savings >= 0) {
      
      vector<Instruction*> bestPack;
      bestPack.push_back(u1);
      bestPack.push_back(u2);
      errs() <<"DU 1." << *u1 << "\n";
      errs() <<"DU 2." << *u2 << "\n";
      
      workPackList.push_back(bestPack);
      //TODO: setAlignment(u1, u2);
      changed = true;
    }
  }
  return changed;
}

void SLP::extendPacklist(BasicBlock &BB) {
  
  //Use worklist (a vector) to do extend Pack List
  vector<vector<Instruction*> > workPackList;
  //Move all pack from global PackSet to worklist
  for (set< vector<Instruction*> > ::iterator it = PackSet.begin(); it != PackSet.end(); it++) {
    vector<Instruction*> Pack = *it;
    workPackList.push_back(Pack);
  }
  //Clean PackSet.
  PackSet.clear();
  while(workPackList.size() > 0) {
    vector<Instruction*> Pack = workPackList[0];
    workPackList.erase(workPackList.begin());
    PackSet.insert(Pack);
    //Now follow the Pack to do def-use use-def extention
    errs() << "Extend Pack[Set]\n";
    printPack(Pack);
    followUseDefs(BB, Pack, workPackList);
    followDefUses(BB, Pack, workPackList);
  }
}

vector<Instruction*> SLP::joinPacks(vector<Instruction*>& Pack1, vector<Instruction*>& Pack2) {
  vector<Instruction*> combinedPack;
  vector<Instruction*>::iterator itr;
  
  combinedPack.insert(combinedPack.end(), Pack1.begin(), Pack1.end());
  combinedPack.insert(combinedPack.end(), Pack2.begin()+1, Pack2.end());
  return combinedPack;
}
void SLP::combinePacks() {
  errs() << "[CombinePacks]Starting combine:"<< PackSet.size() << "\n";
  bool changed = true;
  while(changed) {
    changed = false;
    for (set< vector<Instruction*> > ::iterator it1 = PackSet.begin(); it1 != PackSet.end(); ) {
      bool packsErased = false;
      for (set< vector<Instruction*> > ::iterator it2 = PackSet.begin(); it2 != PackSet.end(); ++it2) {
	vector<Instruction*> Pack1 = *it1;
	vector<Instruction*> Pack2 = *it2;
	if(Pack1.back() == Pack2.front()) {
	  // combine the two packs
	  vector<Instruction*> combinedPack = joinPacks(Pack1, Pack2);
	  
	  // first increment the outerloop iterator so that it points to valid objects in set
	  ++it1;
	  
	  // set this flag to true to indicate that outer loop iterator has been incrmented and need not be incremented again
	  packsErased = true;
	  // erase the two packs and insert the newly created combined pack in PackSet
	  PackSet.erase(Pack1);
	  PackSet.erase(Pack2);
	  //TODO: Free memory occupied by Pack1 and Pack2
	  
	  PackSet.insert(combinedPack);
	  //printPackSet(PackSet);
	  changed = true;
	  // break out of the inner loop as Pack1 has been erased and we need to choose a new Pack1
	  break;
	}
      }
      if(!packsErased) //if packs were not erased increment outer loop as usual
	++it1;
    }
  };
}

//Return the PackSet that contains the instruction
vector<Instruction*> SLP::containingPackSet(Instruction* inst) {
  for(set< vector<Instruction*> >::iterator it=PackSet.begin(); it!=PackSet.end(); it++) {
    vector<Instruction*> Pack = *it;
    for(unsigned i=0; i<Pack.size(); i++) {
      if(inst == Pack[i]) {
         return Pack;
      }
    }
  }
  vector<Instruction*> emptyPack;
  return emptyPack; //Return an empty one
}

//Return the Packset containing the earliest unscheduled statment;
void SLP::splitFirstUnscheduledPack(BasicBlock &BB, set<Instruction*> &ScheduledISet) {
  for (BasicBlock::iterator IR = BB.getInstList().begin(); IR != BB.getInstList().end(); ++IR){
    Instruction* inst = &(*IR);
    if(ScheduledISet.find(inst) == ScheduledISet.end()) { //not scheduled
      vector<Instruction*> Pack = containingPackSet(inst);
      if(Pack.size() > 0) {
        //had to remove this one
        errs() << "[splitFirstUnscheduledPack]Split one Pack\n";
        for(unsigned i=0; i<Pack.size(); i++) {
          errs() << * Pack[i] << "\n";
        }
        PackSet.erase(Pack);
        NumPacksBroken++;
        return;
      }
    }
  }
  return;
}

bool SLP::depsScheduled(set<Instruction*> &UnScheduledISet, Instruction* inst) {
  //Step 1: Check Branch - The last stmt in the BB
  BranchInst * brI;
  if((brI = dyn_cast<BranchInst>(inst))) {
    if(UnScheduledISet.size() == 1) {
        return true; //The last unscheduled unconditional branch at the end of the BB
    }
    else { return false; }
  }

  //Step 2: Phi Node: either operands are out of the BB, or the operand is from the end of the BB.
  if(PHINode::classof(inst)) {
      return true;
  }

  //Step 3: All Operands must be scheduled
  for(unsigned i=0; i<inst->getNumOperands(); i++) {
    if(!Instruction::classof(inst->getOperand(i))) { continue; }
    Instruction* depInst = cast<Instruction>(inst->getOperand(i));
    if(UnScheduledISet.find(depInst) != UnScheduledISet.end()) {
      //the deps are still in unscheduled
      return false;
    }
    //either the inst is not in the BB, or it in the scheduled set
  }
  
  //Step 4: Now check if some memory dependence is violated
  if(IsMemRefInstr(inst)) {
    MemDepResult mdr = MD->getDependency(inst);
    Instruction* depInst = mdr.getInst();
    errs() << "[depsScheduled-MemDep]\n"<< *inst <<"\n"<< *depInst <<"\n";
    
    if(depInst!= NULL) {
      errs() << "[depsScheduled-MemDep]\n"<< *inst <<"\n"<< *depInst <<"\n";
    
      if(UnScheduledISet.find(depInst) != UnScheduledISet.end()) {
	//the deps are still in unscheduled
	errs() << "[depsScheduled-MemDep]Dependence violated\n";
	return false;
      }
    }
  }
//   if(IsMemRefInstr(inst)) {
//     for (list<Instruction*>::iterator IR=UnScheduledIList.begin(); IR!=UnScheduledIList.end(); IR++) {
//       Instruction* inst = *IR;
//       DependenceResult result = analysePair(inst, )
//     
//     }
//   }
  
  return true;

}


bool SLP::schedule(BasicBlock &BB) {
  list<Instruction*> UnScheduledIList; //new basic block sequences;
  set<Instruction*> UnScheduledISet; //new basic block set for fast search
  vector<Instruction*> ScheduledIVector; //new basic block sequences;
  set<Instruction*> ScheduledISet; //new basic block set for fast search

  bool changed = false;
  unsigned attempt = 1;
  unsigned blockNumPacks = 0;
  unsigned blockNumStmtsPacked = 0;


  vector<Instruction*> curScheduled; //scheduled in current iteration
  do{ //until all are scheduled
    //Copy all into unscheduled - rollback to unscheduled status
    UnScheduledIList.clear();
    UnScheduledISet.clear();
    ScheduledIVector.clear();
    ScheduledISet.clear();
    for (BasicBlock::iterator IR = BB.getInstList().begin(); IR != BB.getInstList().end(); ++IR){
      Instruction* inst = &(*IR);
      UnScheduledIList.push_back(inst);
      UnScheduledISet.insert(inst);
    }
    unsigned innerAttempt = 1; //record the inner attempt times
    do { //try some schedule
      errs() << "\n[Schedule]Attempt " << attempt << "-" <<  innerAttempt++ << " started\n";
      curScheduled.clear();
      for(list<Instruction*>::iterator IR=UnScheduledIList.begin(); IR!=UnScheduledIList.end(); IR++) {
        Instruction* inst = *IR;
        if(ScheduledISet.find(inst) != ScheduledISet.end()) { continue; /*was scheduled*/}
        errs() << "[Schedule]Pick:" << *inst << "\n";
        vector<Instruction*> Pack = containingPackSet(inst);
        if(Pack.size() > 0) {
          //need try to
          errs() << ">>Try Schedule Pack:\n";
          bool allDepsScheduled = true;
          for(unsigned i=0; i<Pack.size(); i++) {
            Instruction* packI = Pack[i];
            errs() << ">>>>Pack Pick:" <<  *packI  << "\n";
            if(!depsScheduled(UnScheduledISet, packI)) {
              allDepsScheduled = false;
              break;
            }
          }
          if(allDepsScheduled) { //schedule all insts in the Pack
	    blockNumPacks++;
	    blockNumStmtsPacked += Pack.size();
            for(unsigned i=0; i<Pack.size(); i++) {
              Instruction* packI = Pack[i];
              errs() << "[Schedule]SchedulePack:" << *packI << "\n";
              curScheduled.push_back(packI);
              UnScheduledISet.erase(packI);
              ScheduledIVector.push_back(packI);
              ScheduledISet.insert(packI);
            }
          }
        }
        else { //single inst:
          if(depsScheduled(UnScheduledISet, inst)) {
            errs() << "[Schedule]ScheduleSingle:" << *inst << "\n";
	    //TODO: Putting these 4 instruction in a separate function would improve the code readability.
            curScheduled.push_back(inst);
            UnScheduledISet.erase(inst);
            ScheduledIVector.push_back(inst);
            ScheduledISet.insert(inst);
          }
        }
      } //end for
      //remove all from cur cur-scheduled from UnScheduledIList
      for(unsigned i=0; i<curScheduled.size(); i++) {
        UnScheduledIList.remove(curScheduled[i]);
      }
    } while (curScheduled.size() > 0); //until no additional stmts can be scheduled in current attempt
    errs() << "[Schedule]Finished schedule attempt: "<< attempt++ <<"\tInstructions left unscheduled: "<< UnScheduledIList.size() << "\n\n";
    if(UnScheduledIList.size() == 0) { break; /*all finished*/}

    //No Change, had to remove one PackSet
    blockNumPacks = 0;
    blockNumStmtsPacked = 0;
    //TODO:need use some more complex test case to test
    errs() << "[Schedule]Cannot schedule. Had to split one pack\n";
    splitFirstUnscheduledPack(BB, ScheduledISet);
  } while(true);

  //final step, removing all instructions from the middle, and insert them in the beginning one by one
  if(ScheduledIVector.size() > 0) {
    changed = true;
    for(int i=ScheduledIVector.size()-1; i >=0; i--) {
      BB.getInstList().remove(ScheduledIVector[i]);
      BB.getInstList().insert(BB.getFirstInsertionPt(), ScheduledIVector[i]);
    }
  }

  //Update to global statistics
  NumPacks += blockNumPacks;
  NumStmtsPacked += blockNumStmtsPacked;

  return changed;
}

/*
 * Generating the constant operand for a vector instruction
 * There are two cases
 * 1) The input constants are different: generate a insert element constant expr
 *    to merge all constants
 * 2) The input constants are the same value: just return the constant directly
 *    (suppose the target machine can support vec + scalar instruction)
 */
Constant* SLP::genInsertelementConsts(vector<Constant*> &consts) {
  unsigned vectorSize = consts.size();
  assert(vectorSize > 0);

  Constant* const0 = consts[0];
  //construct the vector type
  VectorType* vectorType = VectorType::get(const0->getType(), vectorSize);

  UndefValue* undefV = UndefValue::get(vectorType);

  Type* i32type = Type::getInt32Ty(const0->getType()->getContext());

  Constant* idx = ConstantInt::get(i32type, 0);
  Constant* insert = ConstantExpr::getInsertElement(undefV, consts[0], idx);
  for(unsigned i=1; i < vectorSize; i++) {
    idx = ConstantInt::get(i32type, i);
    insert = ConstantExpr::getInsertElement(insert, consts[i], idx);
  }
  return insert;

}


Instruction* SLP::genInsertelementInsts(vector<Value*> &insts, vector<Instruction*> &outInsts) {
  unsigned vectorSize = insts.size();
  assert(vectorSize > 0);
  Value* value0 = insts[0];
  VectorType* vectorType = VectorType::get(value0->getType(), vectorSize);
  UndefValue* undefV = UndefValue::get(vectorType);

  Type* i32type = Type::getInt32Ty(value0->getType()->getContext());
  Constant* idx = ConstantInt::get(i32type, 0);
  InsertElementInst* insert = InsertElementInst::Create(undefV, insts[0], idx);
  outInsts.push_back(insert);
  for(unsigned i=1; i<vectorSize; i++){
      idx = ConstantInt::get(i32type, i);
      insert = InsertElementInst::Create(insert, insts[i], idx);
      outInsts.push_back(insert);
  }
  return insert; //also return the last one

}

void SLP::genExtractelementInsts(Instruction* inst, vector<Instruction*> &outInsts) {

  errs() << "[genExtractelementInsts]" << *inst <<" with type "<< *inst->getType() << "\n";
  
  VectorType* vectorType = cast<VectorType>(inst->getType());
  unsigned vectorSize = vectorType->getNumElements();

  Type* i32type = Type::getInt32Ty(inst->getType()->getContext());

  for(unsigned i = 0; i < vectorSize; i++) {
      Constant* idx = ConstantInt::get(i32type, i);
      Instruction* extractInst = ExtractElementInst::Create(inst, idx);
      outInsts.push_back(extractInst);
  }
}

/*
 * The algorithm is
 * 1) get one stmt. In a PackSet? true: next; false just insert the stmt
 * 2) getelement stmt: not need handle,
 * 3) load/store stmt:
 *        ptr, get element, get the first one, and insert one cast
 * 3) Check the operands:
 *       load/store's ptr:  getelement, only use the first one and insert one cast; getelement expr, get bit cast
 *       several virtual register, need create another insert element
 * 4) Replace all the original one with getlement instruction to make it consistent
 */
void SLP::emitCode(BasicBlock &BB) {
  errs() << "[emitCode]Starting.........\n";
  vector<Instruction*> noOutputPackInsts; //all packs no need extract instructions.

  for (BasicBlock::iterator IR = BB.getInstList().begin(); IR != BB.getInstList().end(); ){
    Instruction* inst = &(*IR);
    vector<Instruction*> Pack = containingPackSet(inst);
    if(Pack.size() == 0) {
      errs() << "[emitCode]pass:" << *inst << "\n";
      ++IR; continue;
    } //single inst no any action
    //now the inst is in a pack. And they are isomorphic
    unsigned packSize = Pack.size();

    if(GetElementPtrInst::classof(inst)) {
      //No need handle getelementptr. Reason
      // 1) If the returned addresses are ajacent, they will be handled in load/sotre's operands
      // 2) If the returned addresses are not ajacent, the store/load use them will not be put into a pack. Still no problem
      errs() << "[emitCode]ingore " <<  packSize << " GetElementPtrInsts start with:\n    " << *inst << "\n";
      for(unsigned i=0; i<packSize; IR++, i++);
      continue;
    }
    //For other instrs, we need create a new one
    errs() << "[emitCode]Process Pack(" <<  packSize << ")  start with:\n    " << *inst << "\n";
    Instruction* vecInst = inst->clone();
    //new modify the vecInst's type
    if (!vecInst->getType()->isVoidTy()) {
      VectorType* vectorType = VectorType::get(vecInst->getType(), packSize);
      vecInst->mutateType(vectorType);
      errs() << "[emitCode] modified vecType to: " << *vecInst <<"\n";
    }

    //Grab the ptr operand for later use
    Value* ptrOperand = NULL;
    Type* vecPtrType = NULL;
    if(LoadInst::classof(inst)){
      LoadInst* LI = cast<LoadInst>(inst);
      ptrOperand = LI->getPointerOperand();
      PointerType* ptrTy = cast<PointerType>(ptrOperand->getType());
      Type* eleTy = ptrTy->getElementType();
      vecPtrType = VectorType::get(eleTy, packSize)->getPointerTo();
    }
    if(StoreInst::classof(inst)){
      StoreInst* SI = cast<StoreInst>(inst);
      ptrOperand = SI->getPointerOperand();
      PointerType* ptrTy = cast<PointerType>(ptrOperand->getType());
      Type* eleTy = ptrTy->getElementType();
      vecPtrType = VectorType::get(eleTy, packSize)->getPointerTo();
    }

    //Only use the first instr in the pack to check
    for(unsigned i=0; i<inst->getNumOperands(); i++) {
      Value* operand = inst->getOperand(i);
      Value *vecOperand;
      vector<Instruction*> insertInsts; //used for prepare the operands;
      errs() <<"[emitCode]change operand " <<*operand <<"\n";

      if(Constant::classof(operand)) {
        Constant* constOperand = cast<Constant>(operand);
        if(operand == ptrOperand) {
          vecOperand = ConstantExpr::getBitCast(constOperand, vecPtrType);
        }
        else {
          bool allConstOperand = true;
          //prepare both vecotr<Constant*> and vector<Value*>
          vector<Constant*> constOperands;
          vector<Value*> valueOperands;
          for(unsigned j=0; j<packSize;j++) {
            Value* curOperand = Pack[j]->getOperand(i);
            valueOperands.push_back(curOperand);
            if(allConstOperand && Constant::classof(curOperand)) {
              constOperands.push_back(cast<Constant>(curOperand));
            }
            else{
              allConstOperand = false;
            }
          }
          //now gen the insert operand
          if(allConstOperand) {
            vecOperand = genInsertelementConsts(constOperands);
          }
          else {
            vecOperand = genInsertelementInsts(valueOperands, insertInsts);
          }
        } //non-ptr const operand
      } //const operand
      else {
        if(operand == ptrOperand) {
          errs() << "[emitCode]bitcast: " << *operand << " from type: " << *operand->getType() << " to type: " << *vecPtrType <<"\n";
          CastInst* castInst = CastInst::CreateTruncOrBitCast(operand, vecPtrType);
          vecOperand = castInst;
          errs() << "[emitCode]bitcast done\n";
          insertInsts.push_back(castInst);
        }
        else {
          vector<Value*> valueOperands;
          for(unsigned j=0; j<packSize;j++) {
            Value* curOperand = Pack[j]->getOperand(i);
            valueOperands.push_back(curOperand);
          }
          vecOperand = genInsertelementInsts(valueOperands, insertInsts);
        }
      } //inst operand

      errs() << "[emitCode]insert all operands preparing code\n";
      for(unsigned j = 0; j<insertInsts.size(); j++) {
        BB.getInstList().insert(IR, insertInsts[j]);
      }
      errs() << "[emitCode]trySet Operand " << *vecOperand <<"\n";
      vecInst->setOperand(i, vecOperand);

    } //finish processing operands

    BB.getInstList().insert(IR, vecInst);
    errs() << "[emitCode]inserted vec inst " << *vecInst <<"\n";
    //now gen the bunch of extract
    if(!vecInst->getType()->isVoidTy()) {
      //The original instruction has output, need extract them out
      vector<Instruction*> extractInsts;
      genExtractelementInsts(vecInst, extractInsts);
      //now insert extract and alos replace the original pack with the new one
      for(unsigned j = 0; j<extractInsts.size(); j++) {
        BB.getInstList().insert(IR, extractInsts[j]);
        errs() << "[emitCode]inserted exteact inst " << *extractInsts[j] <<"\n";
        errs() << "[emitCode]replace org inst: " << *inst <<"\n";
        inst->replaceAllUsesWith(extractInsts[j]);
        IR++; //move to next instr in the pack
        inst = &(*IR);
      }
    }
    else {
      //The original instruction has no output, e.g. store, just remove them.
      for(unsigned j = 0; j<Pack.size(); j++) {
        noOutputPackInsts.push_back(Pack[j]);
        IR++;
      }
    }
  } //schedule all instruction
  //And remove no output pack instructions
  for(unsigned j = 0; j<noOutputPackInsts.size(); j++) {
    noOutputPackInsts[j]->dropAllReferences();
  }
  for(unsigned j = 0; j<noOutputPackInsts.size(); j++) {
    noOutputPackInsts[j]->eraseFromParent();
  }
}


bool SLP::runOnBasicBlock(BasicBlock &BB) {

  //TODO: Looks like it is ok to run this pass once for a procedure. Since our's is a BB pass, we are running it again and again for each BB. 
  AA = &getAnalysis<AliasAnalysis>();
  MD = &getAnalysis<MemoryDependenceAnalysis>();
  SE = &getAnalysis<ScalarEvolution>();
  TD = getAnalysisIfAvailable<TargetData>();

  PackSet.clear();
  bool changed = false;
  errs() << "[SLP]runOnBasicBlock(): Input\n" << BB << "\n";
  if(!findAdjRefs(BB)) {
    errs() << "[SLP]No isomorphic statements found.\n\n";
    return false;
  }

  //Found some packs, dump them
  errs() << "[SLP]After findAdjRefs()\n";
  printPackSet(PackSet);

  extendPacklist(BB);

  errs() << "[SLP]After extendPacklist()\n";
  printPackSet(PackSet);

  combinePacks();

  errs() << "[SLP]After combinePacks()\n";
  printPackSet(PackSet);

  changed = schedule(BB);
  errs() << "[SLP]After schedule()";
  if(changed) {
      errs() << "\n" <<BB << "\n";
  }
  else {
      errs() << ": No Changes\n";
  }

  emitCode(BB);
  errs() << "[SLP]After emitCode()\n" << BB << "\n";

  return changed;
}

